package com.tgy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 12/7/20 11:23 AM
 *
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
public class 剑指_Offer_07_重建二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder == null || inorder == null || preorder.length != inorder.length) {

            return null;
        }

        List<Integer> preorderList = Arrays.stream(preorder).boxed().collect(Collectors.toList());

        return generalTree(preorderList,inorder,0,inorder.length);
    }

    private TreeNode generalTree(List<Integer> preorderList, int[] inorderList,int start, int end) {

        if (preorderList.isEmpty()) {

            return null;
        }

        Integer ele = preorderList.remove(0);

        int index = find(inorderList, ele, start, end);
        if (index < 0) {

            return null;
        }

        TreeNode rootNode = new TreeNode(ele);
        if (preorderList.isEmpty()) {

            return rootNode;
        }

        Integer pre = preorderList.get(0);

        if (find(inorderList,pre,start,index) >= 0) {

            rootNode.left = generalTree(preorderList,inorderList,start,index);
        }

        if (preorderList.isEmpty()) {

            return rootNode;
        }

        pre = preorderList.get(0);

        if (find(inorderList,pre,index + 1,end) >= 0) {

            rootNode.right = generalTree(preorderList,inorderList,index+1,end);
        }

        return rootNode;
    }

    private int find(int[] inorderList, int el, int start, int end) {

        if (start == end) {

            return -1;
        }

        int index = -1;

        for (int i = start; i < end; i++) {

            if (inorderList[i] == el) {

                return i;
            }
        }

        return -1;
    }

    private TreeNode generalTree(List<Integer> preorderList, List<Integer> inorderList) {

        if (preorderList.isEmpty()) {

            return null;
        }

        Integer ele = preorderList.remove(0);
        TreeNode rootNode = new TreeNode(ele);

        if (preorderList.isEmpty()) {

            return rootNode;
        }

        int index = inorderList.indexOf(ele) - 1;
        if (index  >= 0 && inorderList.get(index).equals(preorderList.get(0))) {

            rootNode.left = generalTree(preorderList, inorderList);
        }

        index = index + 2;
        if (index < inorderList.size() && inorderList.get(index).equals(preorderList.get(0))) {

            rootNode.right = generalTree(preorderList,inorderList);
        }

        return rootNode;
    }
}
